/*
实验5-3 二叉树直径
分数 25
作者 陈越
单位 浙江大学

树中两个结点间的路径长度，是指从一个结点沿着树中的边走到另一个结点所经过的最少的边数。二叉树的直径是指任意两个结点之间路径长度的最大值。请给出计算二叉树直径的算法。
函数接口定义：

int Diameter(BinaryTree tree);

其中 BinaryTree 相关的数据类型的定义如下：

typedef char TElemSet;
typedef struct BinaryTreeNode *BinaryTree;
struct BinaryTreeNode {
    TElemSet data;      // 数据元素 
    BinaryTree left;    // 左孩子指针 
    BinaryTree right;   // 右孩子指针 
};

函数 Diameter 应返回二叉树 tree 的直径。
输入样例：

11
abdfgijehkc
fdigjbekhac

输出样例：

6
*/

#include <stdio.h>
#include <stdlib.h>

typedef char TElemSet;
typedef struct BinaryTreeNode *BinaryTree;
struct BinaryTreeNode {
    TElemSet data;      /* 数据元素 */
    BinaryTree left;    /* 左孩子指针 */
    BinaryTree right;   /* 右孩子指针 */
};

BinaryTree BuildTree(TElemSet *preorder, TElemSet *inorder, int n)
{ /* 根据前序遍历序列和中序遍历序列构建有n个结点的二叉树 */
    BinaryTree tree;
    int i;
    
    if (n==0) {
        tree = NULL; /* 递归终止条件，空树 */ 
    }
    else {
        /* 建立当前根结点 */
        tree = (BinaryTree)malloc(sizeof(struct BinaryTreeNode));
        tree->data = preorder[0];
        /* 在中序遍历序列中找根结点 */
        for (i=0; i<n; i++) {
            if (inorder[i] == preorder[0])
                break;
        }
        /* 递归构建左右子树 */
        tree->left = BuildTree(preorder+1, inorder, i);
        tree->right = BuildTree(preorder+i+1, inorder+i+1, n-i-1);
    }
    return tree;
}

int Diameter(BinaryTree tree);
 
int main(void)
{
    int n;
    TElemSet *preorder, *inorder;
    BinaryTree tree;
    
    scanf("%d", &n);
    preorder = (TElemSet *)malloc(sizeof(TElemSet) * (n+1));
    scanf("%s", preorder);     
    inorder = (TElemSet *)malloc(sizeof(TElemSet) * (n+1));
    scanf("%s", inorder);
    tree = BuildTree(preorder, inorder, n);
    printf("%d\n", Diameter(tree));
    return 0;
}
/* 你的代码将被嵌在这里 */

int Height(BinaryTree tree) {
    if (tree == NULL) {
        return 0;
    }
    int leftHeight = Height(tree->left);
    int rightHeight = Height(tree->right);
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

int Diameter(BinaryTree tree) {
    if (tree == NULL) {
        return 0;
    }
    int leftHeight = Height(tree->left);
    int rightHeight = Height(tree->right);
    int leftDiameter = Diameter(tree->left);
    int rightDiameter = Diameter(tree->right);

    int maxDiameter = leftDiameter > rightDiameter ? leftDiameter : rightDiameter;
    int rootDiameter = leftHeight + rightHeight;

    if (rootDiameter > maxDiameter) {
        return rootDiameter;
    } else {
        return maxDiameter;
    }
}